﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Analysis_Sorting_Algorithms
{
    class MergeSort
    {
        public int[] RecursiveMerge (int[] array, int left, int right, ref int compare)
        {
            int middle = (left + right) / 2;

            if (right > left) //can still split
            {
                RecursiveMerge(array, left, middle, ref compare);  //spilt left and right sublists again
                RecursiveMerge(array, middle + 1, right, ref compare);
                ActualSorting(array, left, middle + 1, right, ref compare);  //will after previous two recursive calls have returned
            }                                                   //which means all of the sublists smaller than this one will have been sorted already
            return array;
        }

        private void ActualSorting(int[] array, int left, int middle, int right, ref int compare)
        {
            //simulating two sublists using integers as boundries
            //the left list starts with the farthest left element available (left)
            // to one size of the center of the orginal sublist
            //the second sublist starts from the center to the rightmost element of the sublist (right)

            int leftStop = middle - 1;
            int totalElements = right - left + 1;
            int tmpIndex = left;
            int[] tmp = new int[array.Length];

            while (left <= leftStop && middle <= right)//while both sides still have elements to compare
            {
                if (array[left] <= array[middle])//left's current sub-element is smaller than right's current sub-element
                {
                    //add left to a temporary array and move the left 'pointer' to the next elemnt in its sub-list
                    tmp[tmpIndex] = array[left];
                    left++;
                    tmpIndex++;
                    compare++;
                }
                else //rights is bigger so add right element to a temporary array and move right's 'pointer' to the next element in its sub-list
                {
                    tmp[tmpIndex] = array[middle];
                    middle++;
                    tmpIndex++;
                    compare++;
                }
            }

            //At this point either right or left has ran out of elements

                while (left <= leftStop) //left still has elemnts but they are sorted so just add them the temporary list
                {
                    tmp[tmpIndex] = array[left];
                    tmpIndex++;
                    left++;
                }

                while (middle <= right) //right still has elemnts but they are sorted so just add them the temporary list
                {
                    tmp[tmpIndex] = array[middle];
                    middle++;
                    tmpIndex++;
                }

                for (int i = 0; i < totalElements; i++) //transfer sorted values back to orginal array 
                {
                    array[right] = tmp[right];
                    right--;
                }
        }
    }
}
